组合学 Combinatorics

取球问题（Urn Model）

现在有一个盒子，里面有$n$个球（球可分）。我们现在会从里面取$k$次球出来。

我们分4种情况讨论：

1. 球取出来之后不放回去，关注顺序。

那么一共有

$n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}$

种情况。

写成集合：

$\left|\left\{(s_1,\ldots,s_k)\in [n]^k \;\middle|\; \left|\{s_1,s_2,\ldots,s_k\}\right| = k\right\}\right| = \frac{n!}{(n-k)!} =: n^{\underline{k}}$

2. 球取出来之后不放回去，不关注顺序。

那就是相当于从$n$个球中任取$k$个，也就是

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$

写成集合：

$\left|\left\{(s_1,\ldots,s_k)\in [n]^k \;\middle|\; s_1 < s_2 < \cdots < s_k\right\}\right| = \frac{n!}{k!(n-k)!} = \binom{n}{k}$

3. 球取出来之后放回去，关注顺序。

每一次都是$n$个选项，所以就是

$n^k$

写成集合：

$\left|\left\{(s_1,\ldots,s_k)\in [n]^k\right\}\right| = n^k$

4. 球取出来之后放回去，不关注顺序。

相当于就是从$n+k-1$个球中任取$k$个球：

$\binom{n+k-1}{k}$

写成集合：

$\left|\left\{(s_1,\ldots,s_k)\in [n]^k \;\middle|\; s_1 \le s_2 \le \cdots \le s_k\right\}\right| = \binom{n+k-1}{k}$

分配问题

将$n$个球放进$k$个盒子里。

一、球不可分，盒子可分

1. 盒子非空。

可以用隔板法：

假设有$n$个球：

........

我们用|（隔板）来区分不同盒子里的球：

1	..\|..\|...\|.

我们便可以将这个问题转换成：在$n-1$个位置中找任意$k-1$个位置放隔板，也就是

$\binom{n-1}{k-1}$

因为每个盒子不能为空，所以需要从$n-1$个空位中选$k-1$个。

写成集合：

$\left|\left\{(s_1,\ldots,s_k)\in \mathbb{N}^k \;\middle|\; s_1+s_2+\cdots+s_k = n\right\}\right| = \binom{n-1}{k-1}$

2. 盒子可空。

同样用隔板法：

因为盒子可以为空，也就是说多个隔板可以挨在一起，所以可以转换成：在$n+k-1$个位置中找任意$k-1$个位置放隔板，也就是

$\binom{n+k-1}{k-1} = \binom{n+k-1}{n}$

写成集合：

$\left|\left\{(s_1,\ldots,s_k)\in \mathbb{N}_0^k \;\middle|\; s_1+s_2+\cdots+s_k = n\right\}\right| = \binom{n+k-1}{n}$

也可以写成：

$\left|\left\{ \bigl(|f^{-1}(1)|,\ldots,|f^{-1}(k)|\bigr) \;\middle|\; f : [n] \rightarrow [k] \right\}\right| = \binom{n+k-1}{k-1} = \binom{n+k-1}{n}$

二、球可分，盒子不可分

3.盒子非空。（把$[n]$分成$k$个非空、无标号组，组内不考虑顺序。）

由第二类Stirling数表示：

$S_{n,k}$ $S_{n+1,k} = S_{n,k-1} + k S_{n,k}, \qquad S_{n,n} = 1, \qquad S_{n+1,0} = 0$

4. 盒子可空。（分成至多$k$个非空无标号组。假设$n\geq 1$。）

$\sum^k_{i=1}S_{n,i}$

三、球可分，盒子可分

5.盒子非空。（把$[n]$分成$k$个非空、有标号组，组内不考虑顺序。）

$\left|\left\{(s_1,\ldots,s_n)\in [k]^n \;\middle|\; \left|\{s_1,s_2,\ldots,s_n\}\right| = k\right\}\right| = k!\, S_{n,k}$

也可以写成：

$\left|\left\{ \bigl(f^{-1}(1),\ldots,f^{-1}(k)\bigr) \;\middle|\; f : [n] \overset{\text{surjective}}{\longrightarrow} [k] \right\}\right| = \left|\left\{ f : [n] \overset{\text{surjective}}{\longrightarrow} [k] \right\}\right| = k!\, S_{n,k}$

6. 盒子可空。

每个球都可独立选择 $k$ 个盒子之一（$n$个球，每个球有$k$种选择）：

$k^n$

也可以写成：

$\left|\left\{ f : [n] \rightarrow [k] \right\}\right| = k^n$

四、球不可分，盒子不可分

7. 盒子非空。（把整数$n$拆成$k$个正整数之和，不计顺序）

写成集合：

$\left|\left\{(s_1,\ldots,s_k)\in \mathbb{N}^k \;\middle|\; s_1+s_2+\cdots+s_k = n,\; s_1 \le s_2 \le \cdots \le s_k\right\}\right| = |P_{n,k}|$ $|P_{n,k}| = |P_{n-1,k-1}| + |P_{n-k,k}|,\qquad |P_{n,n}| = 1,\qquad |P_{n+1,0}| = 0,\qquad |P_{n,k}| = 0 \text{ falls } k>n$

8. 盒子可空。

等价于把整数$n$拆成至多$k$个正整数之和，不计顺序：

$\sum^k_{i=1}|P_{n,i}|$

五、除此之外

9. $[n]$的排列中，恰好有$k$个循环的个数。

由第一类Stirling数表示：

$s_{n,k}$ $s_{n+1,k} = s_{n,k-1} + n s_{n,k}, \qquad s_{n,n} = 1, \qquad s_{n+1,0} = 0$